package features.advance.leetcode.dynamicProgramming.medium;

/**
 *
 *  152. 乘积最大子数组
 *
 *  难度：中等
 *
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），
 * 并返回该子数组所对应的乘积。
 *
 *
 * 示例 1:
 *
 * 输入: [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 * 示例 2:
 *
 * 输入: [-2,0,-1]
 * 输出: 0
 * 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
 *
 * @author LIN
 * @date 2021-05-24
 */
public class Solution152 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
            @Override
            public int maxProduct(int[] nums) {
                return super.maxProduct(nums);
            }
        };
        int[] nums = {2,3,-2,4};
        int res = solution.maxProduct(nums);
        System.out.println(res);


    }
   static class Solution {
       /**
        * 思路：
        * 一、暴力破解，双层遍历，判断所有结果，取到最小值
        * 二、（连续数组，这个思路不可以）先排序，取最大的两个正数乘积，最小的两个负数的乘积，最大和最小值的乘积
        * 三、 dp[i] = max(dp[i-1],dm[i-1],nums[i])
        *      dm[i] = min(dp[i-1],dm[i-1],nums[i])
        * 四、正反向两次循环，负数的个数是技奇数还是偶数，是否有0
        *
        *
        *
        * @param nums 数组
        * @return 最大的乘积子数组
        */
       public int maxProduct(int[] nums) {
           int max = Integer.MIN_VALUE/2;

           int total = 1;
           for (int num : nums) {
               total *= num;
               max = Math.max(max, total);
               if (total == 0) {
                   total = 1;
               }
           }
           total=1;
           for(int i = nums.length-1;i>=0;i--){
               total*=nums[i];
               max = Math.max(max,total);
               if(total==0){
                   total=1;
               }
           }
           return max;
       }
    }
}
